1. Technical Field
The subject matter disclosed herein relates to creating a stable backlog at an internet router buffer that is under active queue management (AQM) in the face of wireless losses that may be misinterpreted as losses of data due to data congestion at the router.
2. Description of Related Art
Congestion control regulates the amount of data traffic injected by end systems into communication networks, preventing persistent network overloading. In the Internet, it is a task typically implemented jointly by Transmission Control Protocol (TCP) and the queue management algorithms in a distributed manner. Running at the end systems, TCP treats packet losses as a signal of network overloading, and slows or backs off the data flow rate when any losses are detected. Running at an intermediate router, the queue management algorithm monitors the queue length of a router buffer, and drops packets based on buffer occupancy.
Active queue management (AQM) is a class of queue management algorithms first proposed in the 1990s. Contrary to the traditional queue management algorithms that do not drop packets until buffer overflow, AQM probabilistically drops packets before buffer overflow based on a dropping rate determined from the past and/or present queue lengths. This keeps the backlog at router buffers small and desynchronizes the back offs of the end systems. When operating effectively, AQM stabilizes the packet queue around a low level, so that 1) the end-to-end delay can be reduced and the delay jitter can be smoothed out; 2) sufficient buffer space is maintained to absorb traffic with data bursts, and 3) the bottleneck link is kept backlogged and thus fully utilized.
An AQM for maintaining a stable and small queue size by minimizing the uncertainty imposed by any external disturbance using H-infinity control theory is disclosed in the article. Li Yu et al., “Design of parameter tunable robust controller for active queue management based on H-infinity control theory,” Journal of Network and Computer Applications 34 (2011), pp 750-764. The Yu paper discloses a closed-loop feedback system representing the TCP process and AQM strategy where the queue length is used as the output and the reference queue size is used as the input. Communication errors and network congestions are treated as external disturbances. In the paper there is a comparison of the queue size of the proposed AQM controller (R-PID) versus random early detection (RED) and other common AQM controllers, which shows that the Yu controller provides a stable and small queue size. However, this prior art controller only deals with wired networks, i.e. wireless losses are not covered.
The next generation network is expected to be a heterogeneous network of networks, including both wired and wireless components. Wireless networks may extend beyond access networks to backhaul networks, and even backbone networks. The characteristics of wireless links pose great challenges to the existing congestion control mechanisms, which are designed based on certain principles that may not hold in the wireless environment. Most notably, signals propagating over wireless links are subject to severe interference, noise, and propagation loss. Packets transmitted over wireless links may be damaged to an extent beyond the recovery capability of error control codes (if any), and are thus discarded. This constitutes another cause of packet loss, in addition to congestive loss, which was discovered by the present inventors. The implications of wireless losses on the design of congestion control are two-fold.
First, TCP tends to misinterpret wireless losses as congestive losses and backs off or reduces the data flow rate unnecessarily, thereby possibly under utilizing the network capacity. The problem has motivated numerous TCP variants in the literature; but, this is not the focus of the present invention. Rather, it is based on the fact that traditional AQM mechanisms designed for wired networks perform badly in networks with wireless links because packet loss in a wireless network is more commonly due to garbled packets and link disconnect, as wireless links are subject to interference, noise and propagation loss that are not present in wired networks.
Second, the extra source of packet losses may interfere with the normal operation of AQM, which communicates implicitly with TCP via active packet drops. When many TCP flows are sharing a bottleneck wireless link, it is unlikely that a large fraction of them will experience wireless losses simultaneously (unless a link is broken). Thus, spurious back offs due to wireless losses would affect the aggregate transmission of all flows much less severely than when there are only a few flows. The wireless link will still be kept backlogged.
An article by K. Chavan et al., “A Robust Active Queue Management Algorithm for Wireless Network,” shows another AQM algorithm for a bottleneck node in a wireless network. This article can be found at the web site http://www.ee.iitb.ac.in/˜karandi/pubs_dir/preprints/kanchan_ram_belur_karandikar_ieeetcst.pdf. According to this paper a wireless link has a capacity that is time varying due to multipath fading and mobility. It describes a robust controller design method that can maintain the queue length close to an operating point with time varying link capacity as an external disturbance. The design of the controller is based on the H-infinity control method. This design is also compared with the RED algorithm and the proposed AQM on the right (RQM). This prior art also shows a stable queue size and converges much faster than RED. Nevertheless, while this prior art deals with wireless networks, it considers the bandwidth variation in the wireless networks but does not consider wireless losses. Thus, this paper fails to provide a solution for wireless losses (which means the buffer queue may fluctuate under wireless losses).
Random early detection (RED) is one of the most representative AQM algorithms. However, the present inventors have determined that it fails to maintain a stable backlog under wireless losses. As proposed by S. Floyd et al., “Random Early Detection Gateways for Congestion Avoidance,” IEEE Trans. Networking, Vol. 1, No. 4, August 1993, RED demonstrates the inherent advantage of AQM in helping the network operate in the optimal region of high throughput and low delay. However, parameter tunings and new variants of RED invariably adopted the trial-and-error approach due to the difficulties in understanding the dynamics of TCP/AQM.
The fluid models of TCP/AQM provide a basis for systematic design and analysis of AQM. See for example, F. Kelly et al., “Rate Control in Communication Networks: Shadow Prices, Proportional Fairness and Stability,” J of the Operational Research Society, Vol. 49, No. 3, pp. 237-252, March 1998; S. H. Low, et al., “Internet Congestion Control,” IEEE Control Systems Magazine, Vol, 22, No. 1, pp. 28-43, February 2002; and V. Misra et al., “Fluid-based Analysis of a Network of AQM Routers Supporting TCP Flows with an Application to RED,” Comp. Comm. Rev., Vol. 30, No. 4, pp. 151-160, October 2000, which are incorporated herein by reference. The optimization-based approach of Low interprets TCP/AQM as a distributed algorithm for solving a utility maximization problem, subject to capacity constraints. See the Kelly et al. article and S. H. Low, “A Duality Model of TCP and Queue Management Algorithms,” IEEE/ACM Trans. Networking, Vol. 11, No. 4, pp. 525-536, August 2003. The major focus is on the optimal solutions attained at equilibrium. However, transient responses of AQM are mostly ignored.
The control-theoretic approach views Internet congestion control as a non-linear control system. The system is first linearized around its equilibrium so as to analyze the dynamics of TCP/AQM around the equilibrium. This enables parameter tuning of RED and design of new AQM algorithms based on frequency-domain analysis, which is powerful in improving the transient response of AQM and guaranteeing the stability of the linear system. See H. Han et al., “TCP Networks Stabilized by Buffer-Based AQMs,” Proc. of IEEE INOFOCOM, March 2004; C. V. Hollot et al., “Analysis and Design of Controllers for AQM Routers Supporting TCP Flows,” IEEE Trans. Automatic Control, Vol. 47, No. 6, June 2002; and S. H. Low et al., “Linear Stability of TCP/RED and a Scalable Control,” Computer Networks Journal, Vol. 43, No. 5, pp. 633-647, December 2003. The Han article discloses designs with a proportional-integral (PI) controller for the general network topology. However, it focuses on designing a PI controller in wired networks and it uses a non-zero proportional part.
The global stability and region of attraction of Internet congestion control have been studied in the context of a non-linear system. These studies are principally concerned with whether the system will converge to equilibrium starting from a feasible initial status not necessarily close to the equilibrium. Among the studies, one by Fan et al., “Robustness of Network Flow Control against Disturbances and Time-Delay,” Syst. Contr. Lett., Vol. 53, No. 11, pp. 1329, September 2004, examined the robustness of the network flow control against disturbances. Yet, the AQM in Fan is static rate-based, which determines the packet dropping rate as a function of the instantaneous incoming data rate, as opposed to the queue length.
In adapting AQM to wireless networks, the inter-flow fairness in ad-hoc networks should be considered. K. Xu et al., “Enhancing TCP Fairness in Ad Hoc Wireless Networks Using Neighborhood RED,” Proc. of ACM MOBICOM, pp. 16-28, September 2003. This fairness can be improved by virtually aggregating packets queued in those interfering nodes to one queue, and applying AQM to manage the queue. The fairness issue is complementary to the focus of the present invention, i.e. stability and robustness against wireless losses.
Two solutions to the problem of backlog at routers in the face of wireless losses suggest themselves. First, a TCP enhancement could be designed that can fully differentiate between congestive and wireless losses. Unfortunately, this is hardly attainable due to the limited network information available to the end systems. Experiments by the present inventors demonstrate that the performance problem of RED persists when the end systems are running wireless TCP enhancements like TCP-NCL, a serialized timer approach which has been shown to be very successful in differentiating congestive and wireless losses. A second possible solution is to use packet marking instead of packet dropping to signal network congestion. However, a globally enabled marking scheme is impractical due to heterogeneity of the Internet. For example, explicit congestion notification (ECN) is the most widely adopted marking scheme, but is generally disabled by default in several versions of Microsoft Windows.
None of the prior art solutions are designed to cope with the fluctuation in buffer occupancy induced by wireless losses, a problem recently uncovered by the present inventors. Thus it would be beneficial if there were a method for stabilizing the buffer occupancy under wireless losses.